package com.zzs.path.util;

import com.zzs.path.constant.PathConstants;
import com.zzs.path.entity.Edge;
import com.zzs.path.entity.Node;
import com.zzs.path.entity.Route;

import java.util.*;

public class PathUtils {

    /**
     * 旅行家问题：计算最短路径
     * @param graph 地图
     * @param target 点集合（含起点、目标点）
     * @param id 结束点
     *           起点id：返回到起点
     *           -1：停在最后一个目标点
     *           指定点id：经过所有目标点后，前往指定点
     * @param nodeToIndex 节点id 到 下标index 的映射
     * @param nodes 点集合
     * @param edges 边集合，可能需要对路径种类等进行判断
     * @return 返回 路径 及 长度
     *      给定 图、点集合，计算并返回 路径 和 长度
     */
    public static Route TSP(int graph[][], int[] target, int id, Map<Integer, Integer> nodeToIndex, List<Node> nodes, List<Edge> edges){
        if(target == null || target.length == 0){
            System.out.println("目标点数组至少包含一个元素");
        }

        int row = target.length;
        int col = 1 << (row - 1);
        int[][] dp = new int[row][col]; // 保存路径长度
        int[][] prev = new int[row][col]; // 保存前驱节点

        Map<Integer, Integer> nodeToTargetIndex = getNodeToTargetIndex(target); // nodeId 到 targetIndex 的映射
        Map<Integer, List<Integer>> findPath = new HashMap<>(); // 到路径的一个映射
        int findPathIndex = -1;

        // 初始化第一列，值为 目标点 到 起点 的距离
        if(id == PathConstants.STOP_LAST){ // -1：停在最后一个目标点
            for(int i = 0;i<row;i++){
                dp[i][0] = 0;
                //prev[i][0] = -1;
            }
        }else{ // 节点id：无论是 起点 还是 指定点，存放都是到 其他点 到 该点 的距离
            for(int i = 0;i<row; i++){
                int x = nodeToIndex.get(target[i]);
                int y = nodeToIndex.get(id);
                int temp = graph[x][y];
                if( temp == PathConstants.MAX_VALUE ){ // 地图上没有直接关联，需要计算路径
                    // 计算两点间的路径和长度
                    Route route = pointToPoint(graph, x, y, nodes);
                    if(route != null){
                        if(!findPath.containsKey(route.getId())){
                            findPath.put(route.getId(), route.getRouteList()); // 这里存放的是 id集合 的index
                        }
                        prev[i][0] = route.getId();
                        dp[i][0] = route.getDistance();
                    }
                }else{ // 地图上直接关联了
                    prev[i][0] = id; // 注，这里存放的是 id
                    dp[i][0] = temp;
                }
            }
        }


        //return null;

        for(int j = 1;j<col; j++){ // 从第二列开始
            for(int i = 0;i<row; i++){
                if( (i == 0 && j != col-1) || ( i != 0 && j == col - 1 )){
                    continue;
                }
                dp[i][j] = PathConstants.MAX_VALUE;
                if( ((j>>(i-1)) & 1) == 1){ // 集合j中的点包含点i，则无需计算
                    continue;
                }
                int temp = j; // 标记，用于提前终止循环
                for(int k = 1; k<row && temp != 0; k++){ // 找到所有可能，并计算最小值
                    temp = temp >> 1;
                    if( ((j >> (k-1)) & 1) == 0 ){
                        continue;
                    }
                    //if( graph[i][k] != PathConstants.MAX_VALUE && dp[k][j^(1<<(k-1))] != PathConstants.MAX_VALUE
                    //        && ( dp[i][j] == PathConstants.MAX_VALUE || dp[i][j] > graph[i][k] + dp[k][j^(1<<(k-1))] )){
                    //    dp[i][j] = graph[i][k] + dp[k][ j^(1<<(k-1))];
                    //    prev[i][j] = k;
                    //}
                    int indexI = nodeToIndex.get(target[i]), indexK = nodeToIndex.get(target[k]);
                    if( dp[k][j^(1<<(k-1))] == PathConstants.MAX_VALUE ){
                        // 如果

                    }else if( graph[indexI][indexK] == PathConstants.MAX_VALUE ){
                        // 如果 i 到 k 没有直接的路径
                        Route route = pointToPoint(graph, indexI, indexK, nodes); // 注：这里虽获取了，但是可能没有使用上（导致 使用数 <= 缓存数）
                        if(route != null && (
                                dp[i][j] == PathConstants.MAX_VALUE || dp[i][j] > route.getDistance() + dp[k][j^(1<<(k-1))] )){
                            if(!findPath.containsKey(route.getId())){
                                findPath.put(route.getId(), route.getRouteList()); // 注，这里存放的是 id集合 的index
                            }
                            prev[i][j] = route.getId();
                            dp[i][j] = route.getDistance() + dp[k][ j^(1<<(k-1))];
                        }
                    }else if( dp[i][j] == PathConstants.MAX_VALUE || dp[i][j] > graph[indexI][indexK] + dp[k][j^(1<<(k-1))] ){
                        // i 到 k 有直接路径
                        dp[i][j] = graph[indexI][indexK] + dp[k][ j^(1<<(k-1))];
                        prev[i][j] = target[k]; // 注，这里存放的是 id
                    }
                }
            }
        }

        printDP(dp);
        printPrev(prev);
        printFindPath(findPath);
        RouteCacheUtils.printRouteCache();

        Route route = new Route();
        route.setDistance(dp[0][col-1]);
        route.setRouteList(getRouteList(id, prev, findPath, target[0], nodeToTargetIndex));
        return route;

        //return null;
    }

    /**
     * 计算两点之间的路径（尽量最短）（Dijkstra、A*、...）
     * @param graph 地图
     * @param start 起点index
     * @param end 终点index
     * @return 返回最短路径长度
     *
     * 注：计算时，使用的是index，计算结果的路径集合也是index表示的，
     * 但是缓存、查找时，应该转换成对应的id，因为缓存是供多方查询的。
     * 故：该方法返回的 路径集合 是由 节点id 组成的。
     */
    public static Route pointToPoint(int[][] graph, int start, int end,  List<Node> nodes){
        // 1、查询缓存，如果有，直接返回
        Route route = null;
        int startId = nodes.get(start).getId();
        int endId = nodes.get(end).getId();
        route = RouteCacheUtils.get(startId, endId);
        if(route != null){
            return route;
        }

        // 2、如果没有，进行计算
        route = AStarUtils.aStar(graph, start, end, nodes);
        for(int i = 0;i< route.routeList.size();i++){
            // route内的路径集合存放的是 下标index，需要转换为 id
            route.routeList.set(i, nodes.get(route.routeList.get(i)).getId());
        }
        route.setStartId(startId);
        route.setEndId(endId);
        System.out.println("存入缓存："+route);

        // 3、计算完成，缓存<startId/endId, 距离+路径>，并返回
        RouteCacheUtils.put(route);
        return route;
    }

    /**
     * target数组中，将 id 映射到 targetIndex
     * @param target
     * @return
     */
    private static Map<Integer, Integer> getNodeToTargetIndex(int[] target){
        Map<Integer, Integer> nodeToTargetIndex = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            nodeToTargetIndex.put(target[i], i);
        }
        return nodeToTargetIndex;
    }

    /**
     * 根据计算得到的各种数据，整理出最终的路径集合
     * @param id 结束点
     * @param prev 保存前驱节点的数组
     * @param findPath 保存<key, 路径>的映射
     * @param startId 起点
     * @param nodeToTargetIndex 节点id 到 target数组下标 的映射
     * @return 节点id组成的集合
     *
     * 注：需要在视情况将路径进行转换
     * 在 prev 中，
     *      小于0 的是对应的一个 id 的集合（不需转换）
     *      大于0 的是对应的一个 id（
     */
    private static List<Integer> getRouteList(int id, int[][] prev, Map<Integer, List<Integer>> findPath, int startId,
                                              Map<Integer, Integer> nodeToTargetIndex){
        List<Integer> routeList = new ArrayList<>();
        int i = 0, j = prev[0].length - 1;
        int k = prev[i][j];
        routeList.add(startId); // 将开始节点放入
        while( !( (j == 0 ) /*( id == -1 && j == 0 ) || ( k == startId ) || ( k < 0 && findPath.get(k).get(0) == startId ) */)){
            if( k < 0 ){
                List<Integer> tempList = findPath.get(k);
                for(int n = tempList.size() - 2; n >= 0; n--){
                    routeList.add(tempList.get(n));
                }
                k = tempList.get(0);
            }else{
                routeList.add(k);
            }
            i = nodeToTargetIndex.get(k);
            j = j ^ (1 << (i - 1));
            k = prev[i][j];
        }
        if( id != -1){ // -1：停在最后一个目标点即可
            if( k < 0 ){
                List<Integer> tempList = findPath.get(k);
                for(int n = tempList.size() - 2; n >= 0; n--){
                    routeList.add(tempList.get(n));
                }
                //k = tempList.get(0);
            }else{
                routeList.add(k);
            }
        }
        return routeList;
    }

    // 打印 dp
    private static void printDP(int[][] dp){
        System.out.println("\n=== dp ===");
        for(int i = 0; i < dp.length; i++) {
            for(int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println();
        }
    }
    // 打印 prev
    private static void printPrev(int[][] prev){
        System.out.println("\n=== prev ===");
        for(int i = 0; i < prev.length; i++) {
            for(int j = 0; j < prev[i].length; j++) {
                System.out.print(prev[i][j]+"\t");
            }
            System.out.println();
        }
    }
    // 打印路径集合
    private static void printFindPath(Map<Integer, List<Integer>> findPath){
        System.out.println("\n=== findPath ===");
        Set<Map.Entry<Integer, List<Integer>>> entries = findPath.entrySet();
        Iterator<Map.Entry<Integer, List<Integer>>> it = entries.iterator();
        while(it.hasNext()){
            Map.Entry<Integer, List<Integer>> next = it.next();
            System.out.println(next.getKey() + "：" + next.getValue() + "：" + next.getValue().hashCode());
        }
    }


}

